#include <cstdlib>
#include <stack>
#include <utility>
using namespace std;
/*使用辅助栈记录当前最小值*/
class MinStack {
private:
  stack<int> _dataStack;
  stack<int> _assistStack;

public:
  MinStack() {}

  void push(int val) {
    if (_assistStack.empty()) {
      _assistStack.push(val);
    } else {
      if (val <= _assistStack.top()) {
        _assistStack.push(val);
      }
    }
    _dataStack.push(val);
  }

  void pop() {
    if (_dataStack.top() == _assistStack.top()) {
      _assistStack.pop();
    }
    _dataStack.pop();
  }

  int top() { return _dataStack.top(); }

  int getMin() {
    if (_assistStack.empty()) {
      return _dataStack.top();
    }
    return _assistStack.top();
  }
};

/*不使用辅助栈，直接在每个元素中存储当前最小值*/
class MinStack_ {
private:
  using node = pair<int, int>;
  stack<node> _dataStack;

public:
  MinStack_() {}

  void push(int val) {
    if (_dataStack.empty()) {
      _dataStack.push({val, val});
    } else {
      int minValue = min(_dataStack.top().second, val);
      _dataStack.push({val, minValue});
    }
  }

  void pop() { return _dataStack.pop(); }

  int top() { return _dataStack.top().first; }

  int getMin() { return _dataStack.top().second; }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */